Many planning applications must address conflicting plan objectives, such as cost, duration, and resource consumption, and\r\ndecision makers want to know the possible tradeoffs. Traditionally, such problems are solved by invoking a single-objective\r\nalgorithm (such as A*) on multiple, alternative preferences of the objectives to identify nondominated plans. The less-popular\r\nalternative is to delay such reasoning and directly optimize multiple plan objectives with a search algorithm like multiobjective A*\r\n(MOA*). The relative performance of these two approaches hinges upon the number of f -values computed for individual search\r\nnodes. A* may revisit a node several times and compute a different f -value each time. MOA* visits each node once and may\r\ncompute some number of f -values (each estimating the value of a different nondominated solution constructed from the node).\r\nWhile A* does not share f -values between searches for different solutions, MOA* can sometimes find multiple solutions while\r\ncomputing a single f -value per node. The results of extensive empirical comparison show that (i) the performance of multiple\r\ninvocations of a single-objective A* versus a single invocation of MOA* is often worse in time and quality and (ii) that techniques\r\nfor balancing per node cost and exploration are promising.
Loading....